|
In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences. If ''N'' is a substructure of ''M'', one often needs a stronger condition. In this case ''N'' is called an elementary substructure of ''M'' if every first-order σ-formula φ(''a''1, …, ''a''''n'') with parameters ''a''1, …, ''a''''n'' from ''N'' is true in ''N'' if and only if it is true in ''M''. If ''N'' is an elementary substructure of ''M'', ''M'' is called an elementary extension of ''N''. An embedding ''h'': ''N'' → ''M'' is called an elementary embedding of ''N'' into ''M'' if ''h''(''N'') is an elementary substructure of ''M''. A substructure ''N'' of ''M'' is elementary if and only if it passes the Tarski–Vaught test: every first-order formula φ(''x'', ''b''1, …, ''b''''n'') with parameters in ''N'' that has a solution in ''M'' also has a solution in ''N'' when evaluated in ''M''. One can prove that two structures are elementary equivalent with the Ehrenfeucht–Fraïssé games. ==Elementarily equivalent structures== Two structures ''M'' and ''N'' of the same signature σ are elementarily equivalent if every first-order sentence (formula without free variables) over σ is true in ''M'' if and only if it is true in ''N'', i.e. if ''M'' and ''N'' have the same complete first-order theory. If ''M'' and ''N'' are elementarily equivalent, one writes ''M'' ≡ ''N''. A first-order theory is complete if and only if any two of its models are elementarily equivalent. For example, consider the language with one binary relation symbol '<'. The model R of real numbers with its usual order and the model Q of rational numbers with its usual order are elementarily equivalent, since they both interpret '<' as an unbounded dense linear ordering. This is sufficient to ensure elementary equivalence, because the theory of unbounded dense linear orderings is complete, as can be shown by Vaught's test. More generally, any first-order theory has non-isomorphic, elementary equivalent models, which can be obtained via the Löwenheim–Skolem theorem. Thus, for example, there are non-standard models of Peano arithmetic, which contain other objects than just the numbers 0, 1, 2, etc., and yet are elementarily equivalent to the standard model. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Elementary equivalence」の詳細全文を読む スポンサード リンク
|